package com.wtgroup.demo.leetcode.q015_三数之和;

import java.util.*;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/4/28 11:02
 */
public class Q015_Test {

    public static void main(String[] args) {
        int[][] inputs = {
                {-1, 0, 1, 2, -1, -4},
        };
        Q015_Test exe = new Q015_Test();
        for (int[] input : inputs) {
            List<List<Integer>> lists = exe.threeSum(input);
            System.out.println(lists);
        }
    }

    /**
     * 排序 + 双指针 (LC思路)
     * 简洁: 9分;
     * 逻辑: 9分;
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        ArrayList<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (i>0 && nums[i] == nums[i-1]) {
                continue;
            }
            int rest = -nums[i];
            int left = i+1, right = n-1;
            while (left<right) {
                int s = nums[left] + nums[right];
                if (s > rest) { // 偏大, right 左移
                    right = moveRight(nums, left, right);
                } else if (s < rest) { // 偏小, left 右移
                    left = moveLeft(nums, n, left);
                } else {
                    ArrayList<Integer> oneAns = new ArrayList<>();
                    oneAns.add(nums[i]);
                    oneAns.add(nums[left]);
                    oneAns.add(nums[right]);
                    ans.add(oneAns);
                    // left, right 都移动
                    left = moveLeft(nums, n, left);
                    right = moveRight(nums, left, right);
                }
            }
        }

        return ans;
    }

    private int moveLeft(int[] nums, int n, int left) {
        while (++left < n && nums[left] == nums[left - 1]) {}
        return left;
    }

    private int moveRight(int[] nums, int left, int right) {
        while (--right > left && nums[right] == nums[right + 1]) {}
        return right;
    }


    /**
     * [无效]
     * 第一个数固定时, 寻找另外两数之和时, 可以保证不重复. 但是第一个数移动过程中, 三数很难保证不重复.
     * 解决: 升序.
     * 总之, 都需要先排好序. 这就不如排序+双指针来的干脆利索.
     * @param nums
     * @return
     * @deprecated 不能保证3数不重复
     */
    public List<List<Integer>> threeSum_dep(int[] nums) {
        ArrayList<List<Integer>> ans = new ArrayList<>();
        Map<Integer, Integer[]> registry = new HashMap<>();
        int target;
        for (int i = 0; i < nums.length; i++) {
            ArrayList<Integer> oneAns = new ArrayList<>();
            int cur = nums[i];
            target = -cur;
            for (int j = i + 1; j < nums.length; j++) {
                Integer[] infoj = registry.get(nums[j]);
                if (infoj!=null && infoj[1]==1) {
                    // 前面遇到过, 且已经配对成功, pass
                    continue;
                }
                // 接下来, 看 差 有无
                Integer[] info2 = registry.get(target - nums[j]);
                if (info2 != null) {
                    if (info2[1] == 0) { // 有心仪的且名花无主
                        info2[1] = 1; // 标记使用过了
                        oneAns.add(cur);
                        oneAns.add(target - nums[j]);
                        oneAns.add(nums[j]);
                        ans.add(oneAns);
                        oneAns = new ArrayList<>();
                    } // else 和我一样的一对已经有了, 我消失
                } else { // 没有遇到心仪的, 注册, 等待别人心仪我
                    Integer[] f = {nums[j], 0};
                    registry.put(nums[j], f);
                }
            }
        }

        return ans;
    }

}
